package com.lry.basic.algorithm.dp;

/**
 * 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
 * 在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
 * 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
 * 输入： [2,7,9,11,1]
 * 输出： 18
 */
public class Massage {
    public static void main(String[] args) {
        System.out.println(new Massage().massage(new int[]{2, 7, 9, 11, 1}));
    }

    public int massage(int[] nums) {
        if(null==nums||nums.length==0)
            return 0;
        if(nums.length==1)
            return nums[0];
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        int max = Math.max(dp[0],dp[1]);
        for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            if(dp[i]>max){
                max = dp[i];
            }
        }

        return max;
    }
}
